//
// Created by weslywang on 2020/5/1.
//

#include "../common/common.h"

int minimumTotal2(vector<vector<int>> &triangle, int level, int index) {
    int result = 0;
    if (level > triangle.size() - 1 || index > triangle[level].size() - 1) {
        return 0;
    }
    int num1 = triangle[level][index] + minimumTotal2(triangle, level + 1, index);
    int num2 = triangle[level][index] + minimumTotal2(triangle, level + 1, index + 1);
    result = min(num1, num2);
    return result;
}

int minimumTotal_1(vector<vector<int>> &triangle) {
    int x = minimumTotal2(triangle, 0, 0);
    return x;
}

int minimumTotal(vector<vector<int>> &triangle) {
    if (triangle.size() == 0 || triangle[0].size() == 0) {
        return 0;
    }
    for (int i = triangle.size() - 2; i >= 0; i--) {
        for (int k = 0; k < triangle[i].size(); k++) {
            int tmp = INT32_MAX;
            if (k + 1 < triangle[i + 1].size()) {
                tmp = triangle[i + 1][k + 1];
            }
            triangle[i][k] = triangle[i][k] + min(triangle[i + 1][k], tmp);
        }
    }
    return triangle[0][0];
}

int main() {
    Common common;
    vector<vector<int>> data = common.loadData();
    vector<vector<int>> *point = &data;
    for (int i = 1; i <= 6; i++) {
        point++;
        minimumTotal(data);
        cout << "**************" << endl;
    }
    return 0;
}